import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA
 * Description:
 * User: lenovo
 * Date: 2023 -05 -05
 * Time: 19:48
 */
class Imp implements Comparator<Integer>{

    @Override
    public int compare(Integer o1, Integer o2) {
        return o2-o1;
    }
}

/**
 * 思路：
 * 1.将要拿出的K个元素按照大根堆的方式进行入堆
 * 2.从K+1个元素开始每一个元素都要与堆顶元素进行比较：
 * （1）如若元素小于堆顶元素，则抛出堆顶元素然后将此元素入堆
 * （2）如若此元素大于等于堆顶元素，则继续向后寻找新的元素与之进行比较
 * 3.最后保存在此大根堆中的元素就是我们需要的元素，我们只需将它们抛出并保存下来即可。
 */
public class Top_K {
    public static void main(String[] args) {
        Imp imp=new Imp();
        int[] array=new int[]{89,778,15,445,57,6};
        int k=3;
        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(imp);
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(array[i]);
        }
        for (int i = k; i <array.length ; i++) {
            if(priorityQueue.peek()>array[i]){
                priorityQueue.poll();
                priorityQueue.offer(array[i]);
            }
        }
        for (int i = 0; i < k; i++) {
            System.out.println(priorityQueue.poll());
        }
    }


    /**
     * 排序来解决Top_k问题时间复杂度太高，也太没有技术含量
     * 下面利用PriorityQueue来解决虽然比排序要好很多，但是复杂度还是太高
     * @param args
     */
    public static void main2(String[] args) {
        int [] array=new int[]{89,778,15,445,57,6};
        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>();
        for (int i = 0; i < array.length; i++) {
            priorityQueue.offer(array[i]);
        }
        int k=3;
        for (int i = 0; i < k; i++) {
            System.out.println(priorityQueue.poll());
        }
    }
}
